package com.gitee.algorithm.sort;
/*
希尔排序(插入排序的升级):
基本原理：
选择增长量h作为分组依据   外层循环初始化语句：缩进量h刚好等于待插入元素下标索引  例如：对于数组长度是10的，初始增长量为7，依次是7,3,1.
内层循环：就是插入排序，跳着插入提高了效率
注意事项：

 */
public class Shell {
    /*
1.对数组内的元素进行排序
   */
    public static void sort(Comparable[] a) {
    //1根据数组a的长度确定增长量h的初始值
        int h=1;
        while(h<a.length/2){
            h=2*h+1;
        }
    //2希尔排序
        //排序
        while(h>=1){
            //2.1找到待插入元素  缩进量h刚好等于待插入元素下标索引
            for(int i=h;i<a.length;i++){
                //2.2把待插入元素插入到有序序列中
                for(int j=i;j>=h;j-=h){
                    //比较元素
                    if(greater(a[j-h],a[j])){
                        //交换元素
                        exch(a,j-h,j);
                    }else {
                        break;
                    }
                }
            }
            //减小缩进量h
            h=h/2;
        }

    }



    /*
2.判断v是否大于w
     */
    private static boolean greater (Comparable v, Comparable w){
        return v.compareTo(w) > 0;
    }


    /*
3.交换a数组中，索引i和索引j处的值
     */
    private static void exch (Comparable[]a,int i, int j){
        Comparable temp = a[i];
        a[i] = a[j];
        a[j] = temp;

    }
}
